#!/usr/bin/python
# Filename: ex_DSIntro_2_3.py

# order from push and pop

from Stack import Stack

def order(n):
    '''list all possible order of a sequence after push-in and pop-out of stack'''
    def form_order_r(o, r, s):
        # reference can partially be used here,
        # bcz restoration is applied in recursive, which can keep status
        if not r and not s:
            print o, eval_order(o)
        if r:
            # push
            # use copy
            #order = o[:]
            #remain = r[1:]
            #stack = s[:]+r[0:1]
            #form_order(order, remain, stack)
            # use reference
            s.append(r[0])
            form_order_r(o, r[1:], s)
            s.pop()
        if s:
            # pop
            # use copy
            #order = o[:]+s[-1:]
            #remain = r[:]
            #stack = s[:-1]
            #form_order(order, remain, stack)
            # use reference
            o.append(s[-1])
            form_order_r(o, r, s[:-1])
            o.pop()

    def form_order(o, r, s):
        '''in-recursive way to list all possible order'''
        # the most troublesome issue is: 
        # what pushed-in of stack must be new created object not reference, 
        # or else it will be a mass. and this will lead to efficiency problem.
        # remember: stack is to push what to do and deal with the pop,
        # it stores all unsolved status of recursion.
        stack = Stack()
        stack.push((o[:], r[:], s[:]))
        while not stack.is_empty():
            i = stack.pop()
            #print "order: %s, remain: %s, stack:%s" % (i[0], i[1], i[2])
            if len(i[1]) == 0 and len(i[2]) == 0: # remains nothing
                print i[0], verify_order(i[0])
            else:
                # push
                if len(i[1]):
                    i[2].append(i[1][0])
                    stack.push((i[0][:], i[1][1:],i[2][:]))
                    i[2].pop()
                # pop
                if len(i[2]):
                    i[0].append(i[2][-1])
                    stack.push((i[0][:], i[1][:], i[2][:-1]))
                    i[0].pop()
            del i

    order = []
    remain = range(0,n)
    stack = []
    form_order(order, remain, stack)

def verify_order(l):
    '''evaluate whether a list is possible as a sequence pushed-in and pop-out of stack. 
    it required that the original sequence must in ascending order'''
    if len(l) <= 2: return True
    prev = -2
    curr = -3
    m = max(l[-1], l[-2])
    while len(l)+curr >= 0:
        # test later smaller value to be descending order
        # 3 conditions:
        # 1) curr value is smaller than prev, that's obviously ok
        # 2) curr value is bigger than prev, but prev is the biggest in later values, that's ok
        # 3) curr value is bigger than prev, and prev is not the biggest in later values,
        #        then do check, and only prev is need to be checked:
        if l[curr] > l[prev] and l[prev] != m:
            for i in l[prev+1:]:
                if l[prev] < i < l[curr]:
                # later smaller value i is bigger than l[prev]
                    return False
            m = l[curr]
        prev -= 1
        curr -= 1
    return True

order(4)
print "verify_order[1, 4, 2, 3]:", verify_order([1, 4, 2, 3])
print "verify_order[2, 4, 3, 1]:", verify_order([2, 4, 3, 1])
